package _interview75;

/**
 * 1071. 字符串的最大公因子
 */
public class No1071 {
    public String gcdOfStrings(String str1, String str2) {
        int n1 = str1.length();
        int n2 = str2.length();
        int n = gcd(n1, n2);
        String sub = str1.substring(0, n);
        for (int i = n; i < n1; i += n) {
            if (!sub.equals(str1.substring(i, i + n))) return "";
        }
        for (int i = 0; i < n2; i += n) {
            if (!sub.equals(str2.substring(i, i + n))) return "";
        }

        return sub;
    }

    /**
     * 求两数的最大公约数
     * 辗转相除法递归实现
     */
    private int gcd(int a, int b) {
        return b == 0 ? a : gcd(b, a % b);
    }
}
